package a10_动态规划;


/**
 * <p>
 * a31_打家劫舍3
 * </p>
 *
 * @author flyduck
 * @since 2025/2/19
 */
public class a31_打家劫舍3 {
    //dp[0]:不偷当前节点最大金额   dp[1]:偷当前节点最大金额
    //最终的结果：根节点的Math.max(dp[0],dp[1])
    public int rob(TreeNode root) {
        int[] dp = traversal(root);
        return Math.max(dp[0],dp[1]);
    }

    private int[] traversal(TreeNode node){
        if (node == null) {
            return new int[]{0,0};
        }

        int[] leftDp = traversal(node.left);
        int[] rightDp = traversal(node.right);

        //偷当前节点
        int val1 = node.val + leftDp[0] + rightDp[0];
        //不偷当前节点
        int val2 = Math.max(leftDp[0], leftDp[1]) + Math.max(rightDp[0], rightDp[1]);

        return new int[]{val2,val1};
    }
}
